{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Sum of Two Non-Overlapping Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #dynamic-programming #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #动态规划 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSumTwoNoOverlap"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两个非重叠子数组的最大和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和两个整数 <code>firstLen</code> 和 <code>secondLen</code>，请你找出并返回两个非重叠<strong> 子数组 </strong>中元素的最大和<em>，</em>长度分别为 <code>firstLen</code> 和 <code>secondLen</code> 。</p>\n",
    "\n",
    "<p>长度为 <code>firstLen</code> 的子数组可以出现在长为 <code>secondLen</code> 的子数组之前或之后，但二者必须是不重叠的。</p>\n",
    "\n",
    "<p>子数组是数组的一个 <strong>连续</strong> 部分。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,6,5,2,2,5,1,9,4], firstLen = 1, secondLen = 2\n",
    "<strong>输出：</strong>20\n",
    "<strong>解释：</strong>子数组的一种选择中，[9] 长度为 1，[6,5] 长度为 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [3,8,1,3,2,1,8,9,0], firstLen = 3, secondLen = 2\n",
    "<strong>输出：</strong>29\n",
    "<strong>解释：</strong>子数组的一种选择中，[3,8,1] 长度为 3，[8,9] 长度为 2。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,1,5,6,0,9,5,0,3,8], firstLen = 4, secondLen = 3\n",
    "<strong>输出：</strong>31\n",
    "<strong>解释：</strong>子数组的一种选择中，[5,6,0,9] 长度为 4，[0,3,8] 长度为 3。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= firstLen, secondLen &lt;= 1000</code></li>\n",
    "\t<li><code>2 &lt;= firstLen + secondLen &lt;= 1000</code></li>\n",
    "\t<li><code>firstLen + secondLen &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-sum-of-two-non-overlapping-subarrays](https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-sum-of-two-non-overlapping-subarrays](https://leetcode.cn/problems/maximum-sum-of-two-non-overlapping-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[0,6,5,2,2,5,1,9,4]\\n1\\n2', '[3,8,1,3,2,1,8,9,0]\\n3\\n2', '[2,1,5,6,0,9,5,0,3,8]\\n4\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        def help(nums, firstLen, secondLen):\n",
    "            sum_left = 0\n",
    "            for i in range(firstLen):\n",
    "                sum_left += nums[i]\n",
    "            maxsum_left = sum_left\n",
    "            sum_right = 0\n",
    "            for i in range(firstLen, firstLen + secondLen):\n",
    "                sum_right += nums[i]\n",
    "            ans = maxsum_left + sum_right\n",
    "            j = firstLen\n",
    "            for i in range(firstLen + secondLen, len(nums)):\n",
    "                sum_left += nums[j] - nums[j - firstLen]\n",
    "                maxsum_left = max(sum_left, maxsum_left)\n",
    "                sum_right += nums[i] - nums[i - secondLen]\n",
    "                ans = max(ans, maxsum_left + sum_right)\n",
    "                j += 1\n",
    "            return ans\n",
    "        return max(help(nums, firstLen, secondLen), help(nums, secondLen, firstLen))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        return max(self.help(nums,firstLen,secondLen),self.help(nums,secondLen,firstLen))  #一种是长度为firstlen的子数组在前，一种是长度为seconflen的子数组在前\n",
    "    def help(self,nums,firstLen,secondLen):\n",
    "        suml = 0\n",
    "        for i in range(0,firstLen):\n",
    "            suml += nums[i]\n",
    "        maxsuml = suml\n",
    "        sumr = 0\n",
    "        for i in range(firstLen, firstLen + secondLen):\n",
    "            sumr += nums[i]\n",
    "        res = sumr + maxsuml\n",
    "        j = firstLen\n",
    "        for i in range(firstLen + secondLen, len(nums)):\n",
    "            suml += nums[j] - nums[j-firstLen]\n",
    "            maxsuml = max(maxsuml,suml)\n",
    "            sumr += nums[i] - nums[i - secondLen]\n",
    "            res = max(res,maxsuml + sumr)\n",
    "            j += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        return max(self.get_result(nums, firstLen, secondLen),\n",
    "                   self.get_result(nums, secondLen, firstLen))\n",
    "        \n",
    "    def get_result(self, nums, firstLen, secondLen):\n",
    "        max_first = sum(nums[:firstLen])\n",
    "        first_count = max_first\n",
    "        sec_count = sum(nums[firstLen:firstLen+secondLen])\n",
    "        res = max_first + sec_count\n",
    "        \n",
    "        j = firstLen\n",
    "        for i in range(firstLen+secondLen, len(nums)):\n",
    "            first_count += nums[j] - nums[j-firstLen]\n",
    "            max_first = max(max_first, first_count)\n",
    "            sec_count += nums[i] - nums[i-secondLen]\n",
    "            res = max(res, max_first + sec_count)\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        ans = 0\n",
    "        if firstLen+secondLen == len(nums):\n",
    "            return sum(nums)\n",
    "        for i in range(0,len(nums)-firstLen-secondLen+1):\n",
    "            nums_f = nums[i:i+firstLen]\n",
    "            for j in range(i+firstLen,len(nums)-secondLen+1):\n",
    "                nums_s = nums[j:j+secondLen]\n",
    "                ans = max(ans,sum(nums_f)+sum(nums_s))\n",
    "            nums_s = nums[i:i+secondLen]\n",
    "            for k in range(i+secondLen,len(nums)-firstLen+1):\n",
    "                nums_f = nums[k:k+firstLen]\n",
    "                ans = max(ans,sum(nums_f)+sum(nums_s))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], a: int, b: int) -> int:\n",
    "        def cal(a, b):\n",
    "            n = len(nums)\n",
    "            s = [0]*(n+1)\n",
    "            for i in range(1, n+1):\n",
    "                s[i] = s[i-1]+nums[i-1]\n",
    "            \n",
    "            ans, max_a = 0, 0\n",
    "            for i in range(a+b, n+1):\n",
    "                max_a = max(max_a, s[i-b]-s[i-b-a])\n",
    "                ans = max(ans, max_a+s[i]-s[i-b])\n",
    "            \n",
    "            return ans \n",
    "        \n",
    "\n",
    "        return max(cal(a, b), cal(b, a))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = [0] * (n + 1)\n",
    "        for i in range(n):\n",
    "            s[i + 1] = s[i] + nums[i]\n",
    "        ans = 0\n",
    "        l = firstLen\n",
    "        m = secondLen\n",
    "        for i in range(n + 1):\n",
    "            for j in range(n + 1):\n",
    "                if (j - m >= i and i >= l) or (j <= i - l and j >= m):\n",
    "                    if s[i] - s[i - l] + s[j] - s[j - m] > ans:\n",
    "                        ans = s[i] - s[i - l] + s[j] - s[j - m]\n",
    "        return (ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        return max(self.help(nums, firstLen, secondLen), self.help(nums, secondLen, firstLen))\n",
    "\n",
    "    def help(self, nums, firstLen, secondLen):\n",
    "        suml = 0\n",
    "        for i in range(0, firstLen):\n",
    "            suml += nums[i]\n",
    "        maxSumL = suml\n",
    "        sumr = 0\n",
    "        for i in range(firstLen, firstLen + secondLen):\n",
    "            sumr += nums[i]\n",
    "        res = maxSumL + sumr\n",
    "        j = firstLen\n",
    "        for i in range(firstLen + secondLen, len(nums)):\n",
    "            suml += nums[j] - nums[j - firstLen]\n",
    "            maxSumL = max(maxSumL, suml)\n",
    "            sumr += nums[i] - nums[i - secondLen]\n",
    "            res = max(res, maxSumL + sumr)\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        def help(nums, firstLen, secondLen):\n",
    "            suml = sum(nums[:firstLen])\n",
    "            sumr = sum(nums[firstLen:firstLen+secondLen])\n",
    "            maxSuml = suml\n",
    "            res = maxSuml + sumr\n",
    "            for i in range(firstLen, len(nums) - secondLen):\n",
    "                suml += nums[i] - nums[i-firstLen]\n",
    "                maxSuml = max(maxSuml, suml)\n",
    "                sumr += nums[i+secondLen] - nums[i]\n",
    "                res = max(res, maxSuml + sumr)\n",
    "            return res\n",
    "\n",
    "        return max(help(nums, firstLen, secondLen), help(nums, secondLen, firstLen))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def help(self, nums, slow, fast, firstLen, secondLen):\n",
    "        \n",
    "        n, ss, sf = len(nums), 0, 0\n",
    "\n",
    "        while fast + secondLen <= n:\n",
    "            ss = max(ss, sum(nums[slow: slow + firstLen]))\n",
    "            sf = max(sf, sum(nums[fast: fast + secondLen]) + ss)  \n",
    "      \n",
    "            slow += 1\n",
    "            fast += 1\n",
    "        return sf\n",
    "\n",
    "\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        return max(self.help(nums, 0, firstLen, firstLen, secondLen), self.help(nums, 0, secondLen, secondLen, firstLen))\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        # print(s)\n",
    "\n",
    "        ans = 0\n",
    "        def cal(firstLen, secondLen):\n",
    "            nonlocal ans\n",
    "            max_sum_A = 0\n",
    "            for i in range(firstLen + secondLen, len(s)):\n",
    "                max_sum_A = max(max_sum_A, s[i-secondLen] - s[i-secondLen - firstLen])\n",
    "                ans = max(ans, max_sum_A + s[i] - s[i - secondLen])\n",
    "        cal(firstLen, secondLen) \n",
    "        cal(secondLen, firstLen)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pre_sum(self, nums):\n",
    "        res = [nums[0]] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            res[i] = res[i-1] + nums[i]\n",
    "        return res\n",
    "\n",
    "    def pre_max(self, presum, length):\n",
    "        res = [presum[length-1]]\n",
    "        for i in range(length, len(presum)):\n",
    "            cur = presum[i] - presum[i-length]\n",
    "            res.append(max(res[-1], cur))\n",
    "        return res\n",
    "\n",
    "    def sums(self, premax, sufmax, start, end):\n",
    "        res = -float('inf')\n",
    "        # i为第二个子数组的起始位置\n",
    "        for i in range(start, end):\n",
    "            sum1 = premax[i-start]\n",
    "            sum2 = sufmax[i]\n",
    "            res = max(res, sum1+sum2)\n",
    "        return res\n",
    "\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        if firstLen+secondLen == len(nums):\n",
    "            return sum(nums)\n",
    "\n",
    "        # f:first, s:second\n",
    "        presum = self.pre_sum(nums)\n",
    "        pre_max_f = self.pre_max(presum, firstLen)\n",
    "        pre_max_s = self.pre_max(presum, secondLen)\n",
    "\n",
    "        sufsum = self.pre_sum(nums[::-1])\n",
    "        suf_max_f = self.pre_max(sufsum, firstLen)[::-1]\n",
    "        suf_max_s = self.pre_max(sufsum, secondLen)[::-1]\n",
    "        \n",
    "        first_second = self.sums(pre_max_f, suf_max_s, firstLen, len(nums)-secondLen+1)\n",
    "        second_first = self.sums(pre_max_s, suf_max_f, secondLen, len(nums)-firstLen+1)\n",
    "\n",
    "        return max(first_second, second_first)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        return max(self.help(nums, firstLen, secondLen), self.help(nums, secondLen, firstLen))\n",
    "\n",
    "    def help(self, nums, firstLen, secondLen):\n",
    "        suml = 0\n",
    "        for i in range(0, firstLen):\n",
    "            suml += nums[i]\n",
    "        maxSumL = suml\n",
    "        sumr = 0\n",
    "        for i in range(firstLen, firstLen + secondLen):\n",
    "            sumr += nums[i]\n",
    "        res = maxSumL + sumr\n",
    "        j = firstLen\n",
    "        for i in range(firstLen + secondLen, len(nums)):\n",
    "            suml += nums[j] - nums[j - firstLen]\n",
    "            maxSumL = max(maxSumL, suml)\n",
    "            sumr += nums[i] - nums[i - secondLen]\n",
    "            res = max(res, maxSumL + sumr)\n",
    "            j += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        ans = 0\n",
    "        def f(firstLen: int, secondLen: int) -> None:\n",
    "            nonlocal ans\n",
    "            maxSumA = 0\n",
    "            for i in range(firstLen + secondLen, len(s)):\n",
    "                maxSumA = max(maxSumA, s[i - secondLen] - s[i - secondLen - firstLen])\n",
    "                ans = max(ans, maxSumA + s[i] - s[i - secondLen])\n",
    "        f(firstLen, secondLen)  # 左 a 右 b\n",
    "        f(secondLen, firstLen)  # 左 b 右 a\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        pre = list(accumulate(nums, initial = 0))\n",
    "\n",
    "        def cal(firstLen, secondLen):\n",
    "            first = float('-inf')\n",
    "            ret = float('-inf')\n",
    "            for secondEnd in range(firstLen+secondLen, len(pre)):\n",
    "                firstEnd = secondEnd-secondLen\n",
    "                first = max(first, pre[firstEnd]-pre[firstEnd-firstLen])\n",
    "                ret = max(ret, first+pre[secondEnd]-pre[secondEnd-secondLen])\n",
    "            return ret\n",
    "        return max(cal(firstLen, secondLen), cal(secondLen, firstLen))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        def cal(nums):\n",
    "            ans = 0\n",
    "            n = len(nums)\n",
    "            s1, s2 = 0, 0\n",
    "            ms2 = 0\n",
    "            for i in range(n):\n",
    "                s1 += nums[i]\n",
    "                if i >= firstLen:\n",
    "                    s1 -= nums[i - firstLen]\n",
    "                    s2 += nums[i - firstLen]\n",
    "                    if i >= secondLen + firstLen:\n",
    "                        s2 -= nums[i - secondLen - firstLen]\n",
    "                if i >= secondLen + firstLen - 1:\n",
    "                    ms2 = max(ms2, s2)\n",
    "                    ans = max(ans, s1 + ms2)\n",
    "            return ans\n",
    "\n",
    "        return max(cal(nums), cal(nums[::-1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def help(self, nums, slow, fast, firstLen, secondLen):\n",
    "        \n",
    "        n, ss, sf = len(nums), 0, 0\n",
    "\n",
    "        while fast + secondLen <= n:\n",
    "            ss = max(ss, sum(nums[slow: slow + firstLen]))\n",
    "            sf = max(sf, sum(nums[fast: fast + secondLen]) + ss)  \n",
    "      \n",
    "            slow += 1\n",
    "            fast += 1\n",
    "        return sf\n",
    "\n",
    "\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        return max(self.help(nums, 0, firstLen, firstLen, secondLen), self.help(nums, 0, secondLen, secondLen, firstLen))\n",
    "\n",
    "\n",
    "            \n",
    "        \n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "       def check(nums: List[int], n1: int, n2: int) -> int:\n",
    "          n = len(nums)\n",
    "          res = 0\n",
    "          sum1 = 0\n",
    "          max_sum1 = 0\n",
    "          sum2 = 0\n",
    "          for i in range(n1):\n",
    "             sum1 += nums[i]\n",
    "          max_sum1 = sum1\n",
    "          for i in range(n1, n1 + n2):\n",
    "             sum2 += nums[i]\n",
    "          res = sum1 + sum2\n",
    "          for i in range(n1 + n2, n):\n",
    "             sum2 += nums[i]\n",
    "             sum2 -= nums[i - n2]\n",
    "             sum1 += nums[i - n2]\n",
    "             sum1 -= nums[i - n1 - n2]\n",
    "             max_sum1 = max(max_sum1, sum1)\n",
    "             res = max(res, max_sum1 + sum2)\n",
    "          return res\n",
    "       return max(check(nums, firstLen, secondLen), check(nums, secondLen, firstLen))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        ans = 0\n",
    "        def f(firstLen: int, secondLen: int) -> None:\n",
    "            nonlocal ans\n",
    "            maxSumA = 0\n",
    "            for i in range(firstLen + secondLen, len(s)):\n",
    "                maxSumA = max(maxSumA, s[i - secondLen] - s[i - secondLen - firstLen])\n",
    "                ans = max(ans, maxSumA + s[i] - s[i - secondLen])\n",
    "        f(firstLen, secondLen)  # 左 a 右 b\n",
    "        f(secondLen, firstLen)  # 左 b 右 a\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        presum = list(accumulate(nums, initial=0))\n",
    "        def func(firstLen, secondLen):\n",
    "            res = 0\n",
    "            max_sum_first = 0\n",
    "            for i in range(firstLen, len(presum) - secondLen):\n",
    "                max_sum_first = max(max_sum_first, presum[i] - presum[i-firstLen])\n",
    "                res = max(res, max_sum_first + presum[i+secondLen] - presum[i])\n",
    "            return res\n",
    "        return max(func(firstLen, secondLen), func(secondLen, firstLen))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        #a: first length b:second length\n",
    "\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        #print(s)\n",
    "        res=0\n",
    "\n",
    "        def f(a,b):\n",
    "            nonlocal res #f遍历两遍，不断更新res\n",
    "            aMax=0\n",
    "            for i in range(a,len(nums)-b+1):\n",
    "                aMax=max(aMax,s[i]-s[i-a]) \n",
    "                #当sum2为[i:i+b-1]时，sum1的终点可以是i-1,i-2...a-1([0:a-1]是第一个 对应i=a)\n",
    "                # aMax 记录遍历过的sum1的最大值\n",
    "                res=max(res,aMax+s[i+b]-s[i])\n",
    "        f(firstLen,secondLen)\n",
    "        f(secondLen,firstLen)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        maxsum = 0\n",
    "        for i in range(len(nums) - firstLen + 1):\n",
    "            firstSum = 0\n",
    "            for j in range(firstLen):\n",
    "                firstSum += nums[i + j]\n",
    "            karr = []\n",
    "            if i >= secondLen:\n",
    "                karr += list(range(0, i - secondLen))\n",
    "            if i + firstLen + secondLen <= len(nums):\n",
    "                karr += list(range(i + firstLen, len(nums) - secondLen + 1 ))\n",
    "            maxSS = 0\n",
    "            for k in karr:\n",
    "                secondSum = 0\n",
    "                for j in range(secondLen):\n",
    "                    secondSum += nums[k+j]\n",
    "                maxSS = max(maxSS, secondSum)\n",
    "            maxsum = max(firstSum + maxSS, maxsum)\n",
    "        return maxsum\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        ans = maxSumA = maxSumB = 0\n",
    "        for i in range(firstLen + secondLen, len(s)):\n",
    "            maxSumA = max(maxSumA, s[i - secondLen] - s[i - firstLen - secondLen])\n",
    "            maxSumB = max(maxSumB, s[i - firstLen] - s[i - firstLen - secondLen])\n",
    "            ans = max(ans, maxSumA + s[i] - s[i - secondLen], maxSumB + s[i] - s[i - firstLen])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        # dp = []\n",
    "        n = len(nums)\n",
    "        all_len = firstLen + secondLen\n",
    "        ans = sum(nums[:all_len])\n",
    "        pre_sum1 = sum(nums[:firstLen])\n",
    "        pre_sum2 = sum(nums[:secondLen])\n",
    "        start_index = 0\n",
    "        end_sum1 = pre_sum1\n",
    "        end_sum2 = pre_sum2\n",
    "        ans = sum(nums[:all_len])\n",
    "        end_nums_sum1 = ans - pre_sum1\n",
    "        end_nums_sum2 = ans - pre_sum2\n",
    "        for i in range(all_len+1, n+1):\n",
    "            end_nums_sum1 += nums[i-1] - nums[i-secondLen-1]\n",
    "            end_sum1 += nums[start_index + firstLen] - nums[start_index]\n",
    "            pre_sum1 = max(pre_sum1, end_sum1)\n",
    "            \n",
    "            end_nums_sum2 += nums[i-1] - nums[i-firstLen-1]\n",
    "            end_sum2 += nums[start_index + secondLen] - nums[start_index]\n",
    "            pre_sum2 = max(pre_sum2, sum(nums[i-all_len:i-firstLen]))\n",
    "\n",
    "            start_index += 1\n",
    "            ans = max(ans, end_nums_sum1 + pre_sum1, end_nums_sum2 + pre_sum2)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n = len(nums)\n",
    "        slow1, fast1 = 0, firstLen\n",
    "        ss1, sf1 = 0, 0\n",
    "        while fast1 + secondLen <= n:\n",
    "            ss1 = max(ss1, sum(nums[slow1: slow1 + firstLen]))\n",
    "            sf1 = max(sf1, sum(nums[fast1: fast1 + secondLen]) + ss1)  \n",
    "            \n",
    "            \n",
    "            slow1 += 1\n",
    "            fast1 += 1\n",
    "            \n",
    "            \n",
    "        slow2, fast2 = 0, secondLen\n",
    "        ss2, sf2 = 0, 0\n",
    "        while fast2 + firstLen <= n:\n",
    "            ss2 = max(ss2, sum(nums[slow2: slow2 + secondLen]))\n",
    "            sf2 = max(sf2, sum(nums[fast2: fast2 + firstLen]) + ss2)  \n",
    "           \n",
    "            \n",
    "            slow2 += 1\n",
    "            fast2 += 1\n",
    "            \n",
    "        return max(sf1, sf2)\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        return max(self.help(nums, firstLen, secondLen), self.help(nums, secondLen, firstLen))\n",
    "    \n",
    "    def help(self, nums, firstLen, secondLen):\n",
    "        suml = 0\n",
    "        for i in range(0, firstLen):\n",
    "            suml += nums[i]\n",
    "        maxSuml = suml\n",
    "        sumr = 0\n",
    "        for i in range(firstLen, firstLen + secondLen):\n",
    "            sumr += nums[i]\n",
    "        res = maxSuml + sumr\n",
    "        j = firstLen\n",
    "        for i in range(firstLen + secondLen, len(nums)):\n",
    "            suml += nums[j] - nums[j - firstLen]\n",
    "            maxSuml = max(maxSuml, suml)\n",
    "            sumr += nums[i] - nums[i - secondLen]\n",
    "            res = max(res, maxSuml + sumr)\n",
    "            j += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        ans = maxSumA = maxSumB = 0\n",
    "        for i in range(firstLen + secondLen, len(s)):\n",
    "            maxSumA = max(maxSumA, s[i - secondLen] - s[i - firstLen - secondLen])\n",
    "            maxSumB = max(maxSumB, s[i - firstLen] - s[i - firstLen - secondLen])\n",
    "            ans = max(ans, maxSumA + s[i] - s[i - secondLen], maxSumB + s[i] - s[i - firstLen])\n",
    "        return ans\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        preSum = list(accumulate(nums, initial=0))\n",
    "        length = len(nums)\n",
    "        _max = -math.inf\n",
    "        for i in range(length-firstLen-secondLen+1):\n",
    "            j = i+firstLen\n",
    "            for k in range(j, length-secondLen+1):\n",
    "                _sum = (preSum[i+firstLen]-preSum[i]) + (preSum[k+secondLen]-preSum[k])\n",
    "                _max = max(_max, _sum)\n",
    "\n",
    "        for i in range(length-firstLen-secondLen+1):\n",
    "            j = i+secondLen\n",
    "            for k in range(j, length-firstLen+1):\n",
    "                _sum = (preSum[i+secondLen]-preSum[i]) + (preSum[k+firstLen]-preSum[k])\n",
    "                _max = max(_max, _sum)\n",
    "        \n",
    "        return _max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        ans = 0\n",
    "        def f(firstLen: int, secondLen: int) -> None:\n",
    "            nonlocal ans\n",
    "            maxSumA = 0\n",
    "            for i in range(firstLen + secondLen, len(s)):\n",
    "                maxSumA = max(maxSumA, s[i - secondLen] - s[i - secondLen - firstLen])\n",
    "                ans = max(ans, maxSumA + s[i] - s[i - secondLen])\n",
    "        f(firstLen, secondLen)  # 左 a 右 b\n",
    "        f(secondLen, firstLen)  # 左 b 右 a\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n=len(nums)\n",
    "        s=[0]*(n+1)\n",
    "        for i in range(n):\n",
    "            s[i+1]=s[i]+nums[i]\n",
    "        ans=0\n",
    "        def f(f1:int,f2:int):\n",
    "            nonlocal ans\n",
    "            sum1=0\n",
    "            for i in range(0,n-f1-f2+1):\n",
    "                sum1=max(sum1,s[i+f1]-s[i])\n",
    "                sum2=s[i+f1+f2]-s[i+f1]\n",
    "                ans=max(ans,sum1+sum2)\n",
    "        f(firstLen,secondLen)\n",
    "        f(secondLen,firstLen)\n",
    "        return ans\n",
    "            \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n = len(nums)\n",
    "        dp1 = [0] * n\n",
    "        dp2 = [0] * n\n",
    "\n",
    "        for i in range(n-firstLen+1):\n",
    "            dp1[i] = sum(nums[i:i+firstLen])\n",
    "\n",
    "        for i in range(n-secondLen+1):\n",
    "            dp2[i] = sum(nums[i:i+secondLen])\n",
    "\n",
    "        #print(dp1)\n",
    "        #print(dp2)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+secondLen,n):\n",
    "                ans = max(ans,dp2[i]+dp1[j])\n",
    "            for j in range(i+firstLen,n):\n",
    "                ans = max(ans,dp1[i]+dp2[j])\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "#         nlen = len(nums)\n",
    "#         maxpos = nums.index(max(nums))\n",
    "#         maxlen = max(firstLen,secondLen)\n",
    "#         minlen = min(firstLen,secondLen)\n",
    "#         res = []\n",
    "#         for i in range(max(0,maxpos-maxlen+1), min(maxpos+maxlen,nlen)):\n",
    "#             if len(nums[0:i])>=minlen:\n",
    "#                 secpos = nums[0:i].index(max(nums[0:i]))\n",
    "#                 for j in range(max(0,secpos-minlen+1),min(i-minlen+1,secpos+minlen)):\n",
    "#                     res.append(sum(nums[i:i+maxlen])+sum(nums[j:j+minlen]))\n",
    "#             if len(nums[i+maxlen:])>=minlen:\n",
    "#                 secpos = nums[i+maxlen:].index(max(nums[i+maxlen:]))\n",
    "#                 for j in range(max(i+maxlen,i+maxlen+secpos-minlen+1),min(i+maxlen+secpos+minlen,nlen-minlen+1)):\n",
    "#                     res.append(sum(nums[i:i+maxlen])+sum(nums[j:j+minlen]))\n",
    "#         return max(res)\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        ans = maxSumA = maxSumB = 0\n",
    "        for i in range(firstLen + secondLen, len(s)):\n",
    "            maxSumA = max(maxSumA, s[i - secondLen] - s[i - firstLen - secondLen])\n",
    "            maxSumB = max(maxSumB, s[i - firstLen] - s[i - firstLen - secondLen])\n",
    "            ans = max(ans, maxSumA + s[i] - s[i - secondLen], maxSumB + s[i] - s[i - firstLen])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n = len(nums)\n",
    "        def one_way(l, r):\n",
    "            # l是左滑窗的长度，r是右滑窗的长度\n",
    "            sumr = sum(nums[l:l + r])\n",
    "            suml = maxl = sum(nums[:l])\n",
    "            maxtotal = suml + sumr\n",
    "            for i in range(l, n - r):\n",
    "                suml += nums[i] - nums[i - l]\n",
    "                sumr += nums[i + r] - nums[i]\n",
    "                if suml > maxl:\n",
    "                    maxl = suml\n",
    "                if maxl + sumr > maxtotal:\n",
    "                    maxtotal = maxl + sumr\n",
    "            return maxtotal\n",
    "        \n",
    "        return max(one_way(firstLen, secondLen), one_way(secondLen, firstLen))\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n = len(nums)\n",
    "        slow1, fast1 = 0, firstLen\n",
    "        ss1, sf1 = 0, 0\n",
    "        while fast1 + secondLen <= n:\n",
    "            ss1 = max(ss1, sum(nums[slow1: slow1 + firstLen]))\n",
    "            sf1 = max(sf1, sum(nums[fast1: fast1 + secondLen]) + ss1)  \n",
    "            \n",
    "            \n",
    "            slow1 += 1\n",
    "            fast1 += 1\n",
    "            \n",
    "            \n",
    "        slow2, fast2 = 0, secondLen\n",
    "        ss2, sf2 = 0, 0\n",
    "        while fast2 + firstLen <= n:\n",
    "            ss2 = max(ss2, sum(nums[slow2: slow2 + secondLen]))\n",
    "            sf2 = max(sf2, sum(nums[fast2: fast2 + firstLen]) + ss2)  \n",
    "           \n",
    "            \n",
    "            slow2 += 1\n",
    "            fast2 += 1\n",
    "            \n",
    "        return max(sf1, sf2)\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        # 要求的是非重叠且连续的两个子数组\n",
    "        # 所以有两种情况，要么L在前，M在后；要么M在前，L在后\n",
    "        # 所以在便利的过程中分别计算留足余量后的最大值\n",
    "        # 加起来的最大值就是前一个最大值加上后面存在的各种值\n",
    "        L, M = firstLen, secondLen\n",
    "        for i in range(1, len(nums)):\n",
    "            nums[i] += nums[i-1]\n",
    "        res, Lmax, Mmax = nums[L + M - 1], nums[L - 1], nums[M - 1]\n",
    "        for i in range(L+M, len(nums)):\n",
    "            Lmax = max(Lmax, nums[i - M] - nums[i - L - M])\n",
    "            Mmax = max(Mmax, nums[i - L] - nums[i - L - M])\n",
    "            # 分别包括了 L 个子数组在前和 M 个子数组在前\n",
    "            res = max(res, Lmax + nums[i] - nums[i - M], Mmax + nums[i] - nums[i - L])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n = len(nums)\n",
    "        prefix_sum = [0] * (n + 1)\n",
    "\n",
    "        for i in range(1, n + 1):\n",
    "            prefix_sum[i] = prefix_sum[i - 1] + nums[i - 1]\n",
    "\n",
    "        maxCnt = 0\n",
    "\n",
    "        for i in range(n - firstLen - secondLen + 1):\n",
    "            first_sum = prefix_sum[i + firstLen] - prefix_sum[i]\n",
    "\n",
    "            for j in range(n - secondLen + 1):\n",
    "                if j + secondLen < i or i + firstLen <= j:\n",
    "                    second_sum = prefix_sum[j + secondLen] - prefix_sum[j]\n",
    "                    maxCnt = max(maxCnt, first_sum + second_sum)\n",
    "\n",
    "        for i in range(n, firstLen + secondLen - 1, -1):\n",
    "            first_sum = prefix_sum[i] - prefix_sum[i - firstLen]\n",
    "\n",
    "            for j in range(n, secondLen - 1, -1):\n",
    "                if j - secondLen >= i or i - firstLen > j:\n",
    "                    second_sum = prefix_sum[j] - prefix_sum[j - secondLen]\n",
    "                    maxCnt = max(maxCnt, first_sum + second_sum)\n",
    "\n",
    "        return maxCnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "      n=len(nums)\n",
    "      preSum=[0]*(n+1)\n",
    "      #  This function sumulates that the array with firstLen is on the left of that with the secondLen\n",
    "      for i in range(1,n+1):\n",
    "        preSum[i]=preSum[i-1]+nums[i-1]\n",
    "      ret=0\n",
    "      def simulate(firstLen:int,secondLen:int):\n",
    "        nonlocal ret\n",
    "        maxFirstLenSum=0\n",
    "        for i in range(firstLen+secondLen,n+1):\n",
    "          maxFirstLenSum=max(maxFirstLenSum,preSum[i-secondLen]-preSum[i-secondLen-firstLen])\n",
    "          ret=max(ret,maxFirstLenSum+preSum[i]-preSum[i-secondLen])\n",
    "        return ret\n",
    "      simulate(firstLen,secondLen)\n",
    "      simulate(secondLen,firstLen)\n",
    "      return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        q, n, m = [0, *accumulate(nums)], len(nums), firstLen + secondLen\n",
    "        def f(firstLen, secondLen):\n",
    "            cur = 0\n",
    "            return max(q[i] - q[i-secondLen] + (cur := max(cur, q[i-secondLen] - q[i-m])) for i in range(m, n+1))\n",
    "        return max(f(firstLen, secondLen), f(secondLen, firstLen))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        ans = 0\n",
    "        maxSumA = maxSumB = 0\n",
    "\n",
    "        for i in range(firstLen + secondLen, len(s)):\n",
    "            # 维护最大的 左边的 a\n",
    "            maxSumA = max(maxSumA, s[i - secondLen] -\n",
    "                          s[i - secondLen - firstLen])\n",
    "            maxSumB = max(maxSumB, s[i - firstLen] -\n",
    "                          s[i - secondLen - firstLen])\n",
    "            # 更新 目前的 a + b\n",
    "            ans = max(ans, maxSumA + s[i] - s[i - secondLen],\n",
    "                      maxSumB + s[i] - s[i - firstLen])\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        s = list(accumulate(nums, initial=0))\n",
    "        # print(s)\n",
    "\n",
    "        # ans = 0\n",
    "        # def cal(firstLen, secondLen):\n",
    "        #     nonlocal ans\n",
    "        #     max_sum_A = 0\n",
    "        #     for i in range(firstLen + secondLen, len(s)):\n",
    "        #         max_sum_A = max(max_sum_A, s[i-secondLen] - s[i-secondLen - firstLen])\n",
    "        #         ans = max(ans, max_sum_A + s[i] - s[i - secondLen])\n",
    "        # cal(firstLen, secondLen) \n",
    "        # cal(secondLen, firstLen)\n",
    "        # return ans\n",
    "\n",
    "        # 简化 左a右b和右b左a合并到一个循环中\n",
    "        ans = max_sum_A = max_sum_B = 0\n",
    "        for i in range(firstLen + secondLen, len(s)):\n",
    "            max_sum_A = max(max_sum_A, s[i - secondLen] - s[i-secondLen - firstLen]) \n",
    "            max_sum_B = max(max_sum_B, s[i-firstLen] - s[i-secondLen-firstLen])\n",
    "            ans = max(ans, max_sum_A + s[i] - s[i-secondLen], max_sum_B + s[i] - s[i-firstLen])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        s = [0] * (n+1)\n",
    "\n",
    "        for i in range(n):\n",
    "            s[i+1] = s[i] + nums[i]\n",
    "\n",
    "        res = 0\n",
    "        maxSumA = maxSumB = 0   \n",
    "        for i in range(firstLen+secondLen, n+1):\n",
    "            maxSumA = max(maxSumA, s[i-secondLen] - s[i-firstLen-secondLen])\n",
    "            maxSumB = max(maxSumB, s[i-firstLen] - s[i-firstLen-secondLen])\n",
    "            res = max(res, maxSumA + s[i]-s[i-secondLen], maxSumB + s[i] - s[i-firstLen])\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pre_sum(self, nums):\n",
    "        res = [nums[0]] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            res[i] = res[i-1] + nums[i]\n",
    "        return res\n",
    "\n",
    "    def pre_max(self, presum, length):\n",
    "        res = [presum[length-1]]\n",
    "        for i in range(length, len(presum)):\n",
    "            cur = presum[i] - presum[i-length]\n",
    "            res.append(max(res[-1], cur))\n",
    "        return res\n",
    "\n",
    "    def sums(self, premax, sufmax, start, end):\n",
    "        res = -float('inf')\n",
    "        # i为第二个子数组的起始位置\n",
    "        for i in range(start, end):\n",
    "            sum1 = premax[i-start]\n",
    "            sum2 = sufmax[i]\n",
    "            res = max(res, sum1+sum2)\n",
    "        return res\n",
    "\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        # f:first, s:second\n",
    "        presum = self.pre_sum(nums)\n",
    "        pre_max_f = self.pre_max(presum, firstLen)\n",
    "        pre_max_s = self.pre_max(presum, secondLen)\n",
    "\n",
    "        sufsum = self.pre_sum(nums[::-1])\n",
    "        suf_max_f = self.pre_max(sufsum, firstLen)[::-1]\n",
    "        suf_max_s = self.pre_max(sufsum, secondLen)[::-1]\n",
    "        \n",
    "        first_second = self.sums(pre_max_f, suf_max_s, firstLen, len(nums)-secondLen+1)\n",
    "        second_first = self.sums(pre_max_s, suf_max_f, secondLen, len(nums)-firstLen+1)\n",
    "\n",
    "        return max(first_second, second_first)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "在nums中，找到subarray和长度为L1和L2,然后sum of L1 + sum of L2 要是最大的\n",
    "有个限制是L1和L2是不是重叠的\n",
    "\n",
    "所以我们就从头到尾遍历，找到L1在前面，L2在后面的最大sum，和L2在前面，L1在后面的最大sum\n",
    "time: O(N)\n",
    "space: O(1)\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        \"\"\"\n",
    "        辅助函数，枚举长度为len2的子数组，维护其之前长度为len1的子数组的最大元素和\n",
    "        返回两个子数组的最大元素和之和\n",
    "        \"\"\"\n",
    "        def helper(len1: int, len2: int) -> int:\n",
    "            sum_len1 = sum(nums[:len1])  # 计算初始len1长度的子数组的和\n",
    "            max_sum_len1 = sum_len1  # 初始化len1长度的子数组的最大和\n",
    "           \n",
    "            sum_len2 = sum(nums[len1: len1 + len2])  # 计算初始len2长度的子数组的和\n",
    "            max_sum = sum_len1 + sum_len2  # 初始化总的最大和\n",
    "            \n",
    "            for i in range(len1 + len2, len(nums)):\n",
    "                sum_len2 += nums[i] - nums[i - len2]\n",
    "                sum_len1 += nums[i - len2] - nums[i - len1 - len2]\n",
    "                max_sum_len1 = max(max_sum_len1, sum_len1)  # 更新最大值\n",
    "                max_sum = max(max_sum, sum_len2 + max_sum_len1)  # 更新结果\n",
    "                \n",
    "            return max_sum\n",
    "\n",
    "        # 分别执行两种情况：枚举长度为len2的子数组和枚举长度len1的子数组\n",
    "        return max(helper(firstLen, secondLen), helper(secondLen, firstLen))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        def helper(firstLen, secondLen):\n",
    "\n",
    "            first_len_sum = sum(nums[:firstLen])\n",
    "            max_first_len_sum = first_len_sum\n",
    "\n",
    "            second_len_sum = sum(nums[firstLen:firstLen+secondLen])\n",
    "            res = first_len_sum+second_len_sum\n",
    "            for i in range(firstLen+secondLen, len(nums)):\n",
    "                second_len_sum += nums[i]-nums[i-secondLen]\n",
    "                first_len_sum += nums[i-secondLen] - nums[i-firstLen-secondLen]\n",
    "                max_first_len_sum = max(max_first_len_sum, first_len_sum)\n",
    "                res = max(res, second_len_sum+max_first_len_sum)\n",
    "            return res\n",
    "        return max(helper(firstLen, secondLen), helper(secondLen, firstLen))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "# 前缀和\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        s = [0]\n",
    "        for num in nums:\n",
    "            s.append(s[-1] + num)\n",
    "        self.res = -1\n",
    "\n",
    "        def f(firstLen, secondLen):\n",
    "            maxA = -1\n",
    "            for i in range(firstLen + secondLen, len(s)):\n",
    "                maxA = max(maxA, s[i - secondLen] - s[i - secondLen - firstLen])\n",
    "                self.res = max(self.res, s[i] - s[i - secondLen] + maxA)\n",
    "\n",
    "        f(firstLen, secondLen)\n",
    "        f(secondLen, firstLen)\n",
    "        return self.res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        pre = [0] * n\n",
    "        leftmax = [0] * n\n",
    "        rightmax = [0] * n\n",
    "\n",
    "        pre[0] = sum(nums[:firstLen])\n",
    "        for i in range(firstLen, n):\n",
    "            pre[i - firstLen + 1] = pre[i-firstLen] + nums[i] - nums[i - firstLen]\n",
    "\n",
    "        leftmax[0] = pre[0]\n",
    "        for i in range(1, n - firstLen + 1):\n",
    "            leftmax[i] = max(pre[i], leftmax[i - 1])\n",
    "\n",
    "        rightmax[n - firstLen] = pre[n - firstLen]\n",
    "        for i in range(n - firstLen - 1, -1, -1):\n",
    "            rightmax[i] = max(pre[i], rightmax[i + 1])\n",
    "\n",
    "        # 遍历长度为 secondLen 的子数组, 向左向右分别寻找长度为 firstLen 的最大子数组之和\n",
    "        # ans = 0\n",
    "        # print(leftmax)\n",
    "        # print(rightmax)\n",
    "        # print(pre)\n",
    "        p2 = sum(nums[:secondLen])\n",
    "        ans = p2 + rightmax[secondLen]\n",
    "\n",
    "        for j in range(secondLen, n):\n",
    "            p2 += nums[j] - nums[j - secondLen]\n",
    "\n",
    "            # p2 表示的区间为: [i, j], 闭区间\n",
    "            i = j - secondLen + 1\n",
    "            lm = rm = -inf\n",
    "\n",
    "            if i >= firstLen:\n",
    "                lm = leftmax[i - firstLen]\n",
    "\n",
    "            if j < n - firstLen:\n",
    "                rm = rightmax[j + 1]\n",
    "\n",
    "            # print(f'(i, j) = ({i}, {j})')\n",
    "            # print(f'(l, r) = ({lm}, {rm})')\n",
    "            ans = max(ans, lm + p2, rm + p2)\n",
    "            # print(f'ans = {ans}')\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n = len(nums)\n",
    "        # 奇怪的滑动+单调值题目\n",
    "        s = list(accumulate(nums, initial = 0))\n",
    "        def f(fl, sl):\n",
    "            res = 0\n",
    "            leftmax = 0\n",
    "            for i in range(fl + sl, len(s)):\n",
    "                # i is end of right sub\n",
    "                leftmax = max(leftmax, s[i - sl] - s[i - sl - fl])\n",
    "                res = max(res, leftmax + s[i] - s[i - sl])\n",
    "\n",
    "            return res\n",
    "\n",
    "        ans1 = f(firstLen, secondLen)\n",
    "        ans2 = f(secondLen, firstLen)\n",
    "        return max(ans1, ans2)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "        n = len(nums)\n",
    "        def _sum(l):\n",
    "            res = []\n",
    "            i = 0\n",
    "            while i + l <= n:\n",
    "                res.append(pre[i+l] - pre[i])\n",
    "                i += 1\n",
    "            return res\n",
    "        sum1 = _sum(firstLen)\n",
    "        sum2 = _sum(secondLen)\n",
    "\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        while i + firstLen + secondLen <= n:\n",
    "            ans = max(ans, sum1[i] + max(sum2[i+firstLen:n-secondLen+1]))\n",
    "            ans = max(ans, sum2[i] + max(sum1[i+secondLen:n-firstLen+1]))\n",
    "            i += 1\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "\n",
    "        s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        ans = 0\n",
    "        def f(firstLen: int, secondLen: int) -> None:\n",
    "            nonlocal ans\n",
    "            maxSumA = 0\n",
    "            for i in range(firstLen + secondLen, len(s)):\n",
    "                maxSumA = max(maxSumA, s[i - secondLen] - s[i - secondLen - firstLen])\n",
    "                ans = max(ans, maxSumA + s[i] - s[i - secondLen])\n",
    "        f(firstLen, secondLen)  # 左 a 右 b\n",
    "        f(secondLen, firstLen)  # 左 b 右 a\n",
    "        return ans\n",
    "\n",
    "\n",
    "        # pre = list(accumulate(nums,initial = 0))\n",
    "        # n = len(nums)\n",
    "        # i = 0\n",
    "        # ans = 0\n",
    "\n",
    "        # while i+firstLen<=n:\n",
    "        #     j = i+firstLen\n",
    "        #     sumFir = pre[j]-pre[i]\n",
    "        #     while j+secondLen <= n:#pre可以取到n\n",
    "        #         sumSec = pre[j+secondLen] - pre[j]\n",
    "        #         ans = max(ans,sumFir+sumSec)\n",
    "        #         j += 1\n",
    "        #     j = 0\n",
    "        #     while j+secondLen <= i:\n",
    "        #         sumSec = pre[j+secondLen] - pre[j]\n",
    "        #         ans = max(ans,sumFir+sumSec)\n",
    "        #         j += 1\n",
    "        #     i += 1\n",
    "        # return ans \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # l = min(firstLen,secondLen)\n",
    "        # r = max(firstLen,secondLen)\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums,initial=0)) #s = list(accumulate(stones, initial=0))\n",
    "        if firstLen + secondLen == n:\n",
    "            return pre[-1]\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        # print(pre)\n",
    "        while i+firstLen<=n:\n",
    "            j = i + firstLen \n",
    "            firstsum = pre[j] - pre[i]\n",
    "            secendsum = 0\n",
    "            # print(\"fir\",i,firstLen,firstsum,j)\n",
    "            while j+secondLen<=n:\n",
    "                # print(j,j+secondLen)\n",
    "                secendsum = max(secendsum,pre[j+secondLen]-pre[j])\n",
    "                j += 1\n",
    "            j = 0\n",
    "            while j+secondLen<=i:\n",
    "                secendsum = max(secendsum,pre[j+secondLen]-pre[j])\n",
    "                j += 1\n",
    "            # print(\"sec\",secendsum)\n",
    "            ans = max(ans,firstsum+secendsum)\n",
    "            i += 1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #固定长度  显然利用前缀和可以快速求解\n",
    "    #两个子数组的位置关系无非是 A B 或者 B A 先固定A在前，然后枚举B，再固定B枚举A\n",
    "    #在枚举B的过程中，可以同时记录A的和的最大值，使得两者的和始终为最大\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        #求前缀和\n",
    "        preSum = [0]\n",
    "        for num in nums:\n",
    "            preSum.append(preSum[-1] + num)\n",
    "\n",
    "        res = 0\n",
    "        def help(firstLen, secondLen):\n",
    "            maxSumA = 0\n",
    "            nonlocal res\n",
    "            for i in range(firstLen + secondLen, len(preSum)):\n",
    "                maxSumA = max(maxSumA, preSum[i - secondLen] - preSum[i - secondLen - firstLen])\n",
    "                res = max(res, maxSumA + preSum[i] - preSum[i - secondLen])\n",
    "\n",
    "        help(firstLen, secondLen) #先左后右\n",
    "        help(secondLen, firstLen) #先B后A\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        def maxSum(L, M):\n",
    "            maxL = sumL = sum(nums[:L])\n",
    "            maxM = sumM = sum(nums[L : L + M])\n",
    "            total_max = maxL + maxM\n",
    "\n",
    "            for i in range(L + M, len(nums)):\n",
    "                sumL += nums[i - M] - nums[i - M - L]\n",
    "                maxL = max(maxL, sumL)\n",
    "\n",
    "                sumM  += nums[i] - nums[i - M]\n",
    "                total_max = max(total_max, maxL + sumM)\n",
    "            return total_max\n",
    "        \n",
    "        return max(maxSum(firstLen, secondLen), maxSum(secondLen, firstLen))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        N=len(nums)\n",
    "        preSum=[0]*(N+1)\n",
    "        for i in range(N):\n",
    "            preSum[i+1]=preSum[i]+nums[i]\n",
    "        \n",
    "        def f(firstLen, secondLen):\n",
    "            ans=0\n",
    "            max_A = 0\n",
    "            for b_r in range(firstLen+secondLen-1, N):\n",
    "                max_A=max(max_A, preSum[b_r-secondLen+1]-preSum[b_r-secondLen-firstLen+1])\n",
    "                ans = max(ans, max_A + preSum[b_r+1]-preSum[b_r-secondLen+1])\n",
    "            \n",
    "            return ans\n",
    "        return max(f(firstLen, secondLen), f(secondLen, firstLen))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        # 枚举第一段的开始点\n",
    "        # dp[i]表示第一段起点为i时的整个数组的最大值\n",
    "        # dp[i]表示第二段起点为i时的整个数组的最大值\n",
    "\n",
    "        prefix = [0]*(len(nums)+1)\n",
    "        for i in range(1,len(prefix)):\n",
    "            prefix[i] = prefix[i-1] + nums[i-1]\n",
    "        # print(prefix)\n",
    "        # dp2[i]代表以i结尾的第二段的最大值\n",
    "        dp1 = [0]*len(prefix)\n",
    "        for i in range(len(prefix)-secondLen):\n",
    "            dp1[i] = max(prefix[i+secondLen]-prefix[i],dp1[i-1])\n",
    "        # print(dp1)\n",
    "        dp2 = [0]*len(prefix)\n",
    "        for i in range(len(prefix)-secondLen-1,-1,-1):\n",
    "            dp2[i] = max(prefix[i+secondLen]-prefix[i],dp2[i+1])\n",
    "\n",
    "        res = -inf\n",
    "        # secondle在后\n",
    "        for i in range(len(prefix)-firstLen-secondLen):\n",
    "            res = max(res,prefix[i+firstLen]-prefix[i]+dp2[i+firstLen])\n",
    "       \n",
    "        # secondle在前 \n",
    "        for i in range(len(prefix)-firstLen-1,-1,-1):\n",
    "            res = max(res,prefix[i+firstLen]-prefix[i]+dp1[i-secondLen])\n",
    "            # print(prefix[i+firstLen]-prefix[i],dp1[i-secondLen])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        arr=[0]\n",
    "        temp,ans,ma,mb=0,0,0,0\n",
    "        for i in nums:\n",
    "            temp+=i\n",
    "            arr.append(temp)\n",
    "        \n",
    "        for i in range(firstLen+secondLen,len(arr)):\n",
    "            ma=max(ma,arr[i-secondLen]-arr[i-firstLen-secondLen])\n",
    "            mb=max(mb,arr[i-firstLen]-arr[i-firstLen-secondLen])\n",
    "            ans=max(ans,ma+arr[i]-arr[i-secondLen],mb+arr[i]-arr[i-firstLen])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        presum = list(accumulate(nums, initial=0))\n",
    "        def func(firstLen, secondLen):\n",
    "            res = 0\n",
    "            max_sum_first = 0\n",
    "            for i in range(firstLen + secondLen, len(presum)):\n",
    "                max_sum_first = max(max_sum_first, presum[i-secondLen] - presum[i-firstLen-secondLen])\n",
    "                res = max(res, max_sum_first + presum[i] - presum[i-secondLen])\n",
    "            return res\n",
    "        return max(func(firstLen, secondLen), func(secondLen, firstLen))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        m = 0\n",
    "        for s1 in range(len(nums)-firstLen+1):\n",
    "            sum_1 = sum(nums[s1:s1+firstLen])\n",
    "            if s1>=secondLen:\n",
    "                for s2 in range(s1+1-secondLen):\n",
    "                    sum_2 = sum(nums[s2:s2+secondLen])\n",
    "                    if sum_1+sum_2 > m:\n",
    "                        m = sum_1+sum_2\n",
    "            if len(nums)-secondLen-firstLen-s1>=0:\n",
    "                for s2 in range(s1+firstLen,len(nums)-secondLen+1):\n",
    "                    sum_2 = sum(nums[s2:s2+secondLen])\n",
    "                    if sum_1+sum_2 > m:\n",
    "                        m = sum_1+sum_2\n",
    "        return m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        \"\"\"\n",
    "        结果的计算方式为：\n",
    "        i < j < n < m\n",
    "        pre_sub = S[j]-S[i]\n",
    "        nxt_sub = S[n]-S[m]\n",
    "\n",
    "        \"\"\"\n",
    "        def pre_sum(nums, length):\n",
    "            pre = sum(nums[:length])\n",
    "            res = [pre]\n",
    "            for i in range(length, len(nums)):\n",
    "                # print(f\"cur = {res[-1]} + {nums[i]} - {nums[i-length]}\")\n",
    "                cur = pre + nums[i] - nums[i-length]\n",
    "                if cur > res[-1]:\n",
    "                    res.append(cur)\n",
    "                else:\n",
    "                    res.append(res[-1])\n",
    "                pre = cur\n",
    "            return res\n",
    "        \n",
    "        # if firstLen+secondLen == len(nums):\n",
    "        #     return sum(nums)\n",
    "\n",
    "        pre_max_f = pre_sum(nums, firstLen)\n",
    "        print(f\"pre_max_f: {pre_max_f}\")\n",
    "        pre_max_s = pre_sum(nums, secondLen)\n",
    "        print(f\"pre_max_s: {pre_max_s}\")\n",
    "        suf_max_f = pre_sum(nums[::-1], firstLen)[::-1]\n",
    "        print(f\"suf_max_f: {suf_max_f}\")\n",
    "        suf_max_s = pre_sum(nums[::-1], secondLen)[::-1]\n",
    "        print(f\"suf_max_s: {suf_max_s}\")\n",
    "        \n",
    "        # f s\n",
    "        fs = sf = -float('inf')\n",
    "        for i in range(firstLen, len(nums)-secondLen+1):\n",
    "            num1 = pre_max_f[i-firstLen]\n",
    "            num2 = suf_max_s[i]\n",
    "            fs = max(fs, num1+num2)\n",
    "        \n",
    "        for i in range(secondLen, len(nums)-firstLen+1):\n",
    "            num1 = pre_max_s[i-secondLen]\n",
    "            num2 = suf_max_f[i]\n",
    "            sf = max(sf, num1+num2)\n",
    "        print(fs, sf)\n",
    "        return max(fs, sf)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "\n",
    "        # s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        # ans = 0\n",
    "        # def f(firstLen: int, secondLen: int) -> None:\n",
    "        #     nonlocal ans\n",
    "        #     # maxSumA = 0\n",
    "        #     # for i in range(firstLen + secondLen, len(s)):\n",
    "        #     #     maxSumA = max(maxSumA, s[i - secondLen] - s[i - secondLen - firstLen])\n",
    "        #     #     ans = max(ans, maxSumA + s[i] - s[i - secondLen])\n",
    "        # f(firstLen, secondLen)  # 左 a 右 b\n",
    "        # f(secondLen, firstLen)  # 左 b 右 a\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        pre = list(accumulate(nums,initial = 0))\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        maxSumB = 0\n",
    "        while i+firstLen<=n:\n",
    "            j = i+firstLen\n",
    "            sumFir = pre[j]-pre[i]\n",
    "            while j+secondLen <= n:#pre可以取到n\n",
    "                sumSec = pre[j+secondLen] - pre[j]\n",
    "                ans = max(ans,sumFir+sumSec)\n",
    "                j += 1\n",
    "            #此处可用贪心记录左边的最大值\n",
    "            if secondLen <= i:\n",
    "                maxSumB = max(maxSumB,pre[i]-pre[i-secondLen])\n",
    "            ans = max(ans,sumFir+maxSumB)\n",
    "            i += 1\n",
    "        return ans \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # l = min(firstLen,secondLen)\n",
    "        # r = max(firstLen,secondLen)\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums,initial=0)) #s = list(accumulate(stones, initial=0))\n",
    "        if firstLen + secondLen == n:\n",
    "            return pre[-1]\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        # print(pre)\n",
    "        while i+firstLen<=n:\n",
    "            j = i + firstLen \n",
    "            firstsum = pre[j] - pre[i]\n",
    "            secendsum = 0\n",
    "            # print(\"fir\",i,firstLen,firstsum,j)\n",
    "            while j+secondLen<=n:\n",
    "                # print(j,j+secondLen)\n",
    "                secendsum = max(secendsum,pre[j+secondLen]-pre[j])\n",
    "                j += 1\n",
    "            j = 0\n",
    "            while j+secondLen<=i:\n",
    "                secendsum = max(secendsum,pre[j+secondLen]-pre[j])\n",
    "                j += 1\n",
    "            # print(\"sec\",secendsum)\n",
    "            ans = max(ans,firstsum+secendsum)\n",
    "            i += 1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        # 获取数组长度\n",
    "        n = len(nums)\n",
    "        # 计算以i结尾长度为len的连续子数组的和\n",
    "        dp = [[0,0] for _ in range(n)]\n",
    "        # dp[i][0]表示以i结尾，长度为firstlen的连续子数组和\n",
    "        # dp[i][1]表示以i结尾，长度为secondlen的连续子树组和        \n",
    "        for i in range(n):\n",
    "            if i+1 >= firstLen:\n",
    "                dp[i][0] = sum(nums[i+1-firstLen:i+1])\n",
    "            if i+1 >= secondLen:\n",
    "                dp[i][1] = sum(nums[i+1-secondLen:i+1])\n",
    "        # 获得相应连续数组和的列表后进行遍历\n",
    "        max_sum = 0\n",
    "        for i in range(n):\n",
    "            # 第二个数组在右边\n",
    "            if i + secondLen < n:\n",
    "                for j in range(i+secondLen,n):\n",
    "                    max_sum = max(max_sum,dp[i][0] + dp[j][1])\n",
    "            # 第二个数组在左边\n",
    "            if i - firstLen >= 0:\n",
    "                for j in range(0,i-firstLen):\n",
    "                    max_sum = max(max_sum,dp[i][0] + dp[j][1])\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "\n",
    "        pre = list(accumulate(nums,initial = 0))\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        while i+firstLen<=n:\n",
    "            j = i+firstLen\n",
    "            sumFir = pre[j]-pre[i]\n",
    "            while j+secondLen <= n:#pre可以取到n\n",
    "                sumSec = pre[j+secondLen] - pre[j]\n",
    "                ans = max(ans,sumFir+sumSec)\n",
    "                j += 1\n",
    "            j = 0\n",
    "            while j+secondLen <= i:\n",
    "                sumSec = pre[j+secondLen] - pre[j]\n",
    "                ans = max(ans,sumFir+sumSec)\n",
    "                j += 1\n",
    "            i += 1\n",
    "        return ans \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # l = min(firstLen,secondLen)\n",
    "        # r = max(firstLen,secondLen)\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums,initial=0)) #s = list(accumulate(stones, initial=0))\n",
    "        if firstLen + secondLen == n:\n",
    "            return pre[-1]\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        # print(pre)\n",
    "        while i+firstLen<=n:\n",
    "            j = i + firstLen \n",
    "            firstsum = pre[j] - pre[i]\n",
    "            secendsum = 0\n",
    "            # print(\"fir\",i,firstLen,firstsum,j)\n",
    "            while j+secondLen<=n:\n",
    "                # print(j,j+secondLen)\n",
    "                secendsum = max(secendsum,pre[j+secondLen]-pre[j])\n",
    "                j += 1\n",
    "            j = 0\n",
    "            while j+secondLen<=i:\n",
    "                secendsum = max(secendsum,pre[j+secondLen]-pre[j])\n",
    "                j += 1\n",
    "            # print(\"sec\",secendsum)\n",
    "            ans = max(ans,firstsum+secendsum)\n",
    "            i += 1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n=len(nums)\n",
    "        pre,sur=[-inf]*n,[-inf]*n\n",
    "        pre1=pre[firstLen-1]=sum(nums[:firstLen])\n",
    "        sur1=sur[-firstLen]=sum(nums[-firstLen:])\n",
    "        for i in range(firstLen,n):\n",
    "            pre1+=nums[i]-nums[i-firstLen]\n",
    "            sur1+=nums[n-1-i]-nums[n-1-i+firstLen]\n",
    "            pre[i]=max(pre[i-1], pre1)\n",
    "            sur[n-1-i]=max(sur[n-i],sur1)\n",
    "        pre2=sum(nums[:secondLen])\n",
    "        mx=pre2+sur[secondLen]\n",
    "        for i in range(secondLen,n):\n",
    "            pre2+=nums[i]-nums[i-secondLen]\n",
    "            if i-secondLen>=firstLen-1:\n",
    "                mx=max(mx, pre2+pre[i-secondLen])\n",
    "            if n-i-1>=firstLen:\n",
    "                mx=max(mx,pre2+sur[i+1])\n",
    "        return mx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        f_num = self.calculate_sum(nums, firstLen)\n",
    "        s_num = self.calculate_sum(nums, secondLen)\n",
    "\n",
    "        # 计算最大和\n",
    "        res = 0\n",
    "        for f in range(len(f_num)):\n",
    "            # 表示 nums[f: f + firstLen + 1] 之和\n",
    "            f_sum = f_num[f]\n",
    "            for s in range(len(s_num)):\n",
    "                # 表示 nums[s: s + secondLen + 1] 之和\n",
    "                s_sum = s_num[s]\n",
    "                # 确保不会相交\n",
    "                if f <= s < f + firstLen - 1 or f <= s + secondLen - 1 < f + firstLen:\n",
    "                    continue\n",
    "                if s <= f < s + secondLen - 1 or s <= f + firstLen - 1 < s + secondLen:\n",
    "                    continue\n",
    "                res = max(res, f_sum + s_sum)\n",
    "        return res\n",
    "\n",
    "    def calculate_sum(self, nums, k):\n",
    "        res = []\n",
    "        t_sum = 0\n",
    "        left = 0\n",
    "        for right, c in enumerate(nums):\n",
    "            t_sum += c\n",
    "            if right >= k:\n",
    "                t_sum -= nums[left]\n",
    "                left += 1\n",
    "            res.append(t_sum)\n",
    "        return res[k - 1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import *\n",
    "from itertools import *\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        preSum = list(accumulate([0] + nums))\n",
    "        n = len(nums)\n",
    "        ans = float('-inf')\n",
    "        for i in range(n):\n",
    "            # 先找第一部分\n",
    "            if i + firstLen < n:\n",
    "                firstSum = preSum[i+firstLen] - preSum[i]\n",
    "                if i + firstLen + secondLen <= n:\n",
    "                    for j in range(i + firstLen, n - secondLen + 1):\n",
    "                        secondSum = preSum[j+secondLen] - preSum[j]\n",
    "                        ans = max(ans, firstSum + secondSum)\n",
    "            # 先找第二部分\n",
    "            if i + secondLen < n:\n",
    "                secondSum = preSum[i+secondLen] - preSum[i]\n",
    "                if i + secondLen + firstLen <= n:\n",
    "                    for j in range(i + secondLen, n - firstLen + 1):\n",
    "                        firstSum = preSum[j+firstLen] - preSum[j]\n",
    "                        ans = max(ans, firstSum + secondSum)\n",
    "        return ans\n",
    "    def maxSumTwoNoOverlap_error_1(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n = len(nums)\n",
    "        firstList, secondList = [], []\n",
    "        preSum = list(accumulate([0] + nums))\n",
    "        for i in range(n):\n",
    "            if i + firstLen <= n:\n",
    "                firstList.append((-(preSum[i+firstLen] - preSum[i]), i, i+firstLen))\n",
    "            if i + secondLen <= n:\n",
    "                secondList.append((-(preSum[i+secondLen] - preSum[i]), i, i+secondLen))\n",
    "        # 优先第一个栈\n",
    "        def help(firstList, secondList):\n",
    "            ans = float('-inf')\n",
    "            firstHeap = firstList[::]\n",
    "            secondHeap = secondList[::]\n",
    "            while firstHeap and secondHeap:\n",
    "                heapq.heapify(firstHeap)\n",
    "                heapq.heapify(secondHeap)\n",
    "                nextHeapList = secondHeap[1:]\n",
    "                firstSum, firstStartIdx, firstEndIdx = heapq.heappop(firstHeap)\n",
    "                secondSum, secondStartIdx, secondEndIdx = heapq.heappop(secondHeap)\n",
    "                while secondHeap and ((firstStartIdx <= secondStartIdx <= firstEndIdx) or (firstStartIdx <= secondEndIdx <= firstEndIdx)):\n",
    "                    secondSum, secondStartIdx, secondEndIdx = heapq.heappop(secondHeap)\n",
    "                if not (firstStartIdx <= secondStartIdx <= firstEndIdx) and not (firstStartIdx <= secondEndIdx <= firstEndIdx):\n",
    "                    ans = max(ans, - firstSum - secondSum)\n",
    "                secondHeap = nextHeapList\n",
    "                if not secondHeap:\n",
    "                    break\n",
    "            return ans\n",
    "        ans = max(help(firstList[::], secondList[::]), help(secondList[::], firstList[::]))\n",
    "        return ans\n",
    "    def maxSumTwoNoOverlap_error2(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        preSum = list(accumulate([0] + nums))\n",
    "        n = len(nums)\n",
    "        @lru_cache(None)\n",
    "        def dfs(curIdx, sum1, sum2, lenCnt1, lenCnt2):\n",
    "            if curIdx == n:\n",
    "                if lenCnt1 + lenCnt2 == firstLen + secondLen:\n",
    "                    return sum1 + sum2\n",
    "                return float('-inf')\n",
    "            ans = float('-inf')\n",
    "            # 不选择\n",
    "            ans = max(ans, dfs(curIdx+1, sum1, sum2, lenCnt1, lenCnt2))\n",
    "            # 先选择first长度\n",
    "            if not lenCnt1 and curIdx + firstLen <= n:\n",
    "                ans = max(ans, dfs(curIdx+firstLen, preSum[curIdx+firstLen] - preSum[curIdx], sum2, firstLen, lenCnt2))\n",
    "            # 选择second长度\n",
    "            if not secondLen and curIdx + secondLen <= n:\n",
    "                ans = max(ans, dfs(curIdx+secondLen, sum1, preSum[curIdx+secondLen] - preSum[curIdx], lenCnt1, secondLen))\n",
    "            return ans\n",
    "        return dfs(0, 0, 0, 0, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:    \n",
    "        n = len(nums)\n",
    "        prefix = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            prefix[i+1] = prefix[i] + nums[i]\n",
    "        ans = 0\n",
    "        def f(firstLen,secondLen):\n",
    "            nonlocal ans\n",
    "            maxSumA = 0\n",
    "            for i in range(firstLen + secondLen,n+1):\n",
    "                maxSumA = max(maxSumA,prefix[i-secondLen] - prefix[i-secondLen-firstLen])\n",
    "                ans = max(ans,maxSumA + prefix[i] - prefix[i-secondLen])\n",
    "        f(firstLen,secondLen)\n",
    "        f(secondLen,firstLen)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        la =[0]\n",
    "        for v in nums:la.append(v+la[-1])\n",
    "        n=len(nums);big =0\n",
    "        #动态规划\n",
    "        left =[0]*secondLen\n",
    "        w=0 \n",
    "        for i in range(secondLen,n):\n",
    "            if (v:=la[i]-la[i-secondLen])>w:w=v\n",
    "            left.append(w)\n",
    "        right=[0]*(n+1)   \n",
    "        w=0\n",
    "        for j in range(n-secondLen,-1,-1):\n",
    "            if (v:=la[j+secondLen] -la[j])>w:w=v\n",
    "            right[j]=w\n",
    "        for i in range(firstLen,n+1):\n",
    "            p=la[i]-la[i-firstLen]\n",
    "            t=max(left[i-firstLen],right[i])\n",
    "            if t+p >big:big =t+p\n",
    "        return big"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n = len(nums)\n",
    "        prefix_sum = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            prefix_sum[i+1] = prefix_sum[i] + nums[i]\n",
    "        max_sum = 0\n",
    "        first_sum, second_sum = 0, 0\n",
    "        for i in range(firstLen, n - secondLen + 1):\n",
    "            first_sum = max(first_sum, prefix_sum[i] - prefix_sum[i-firstLen])\n",
    "            max_sum = max(max_sum, first_sum + prefix_sum[i + secondLen] - prefix_sum[i])\n",
    "        for j in range(secondLen, n - firstLen + 1):\n",
    "            second_sum = max(second_sum, prefix_sum[j] - prefix_sum[j-secondLen])\n",
    "            max_sum = max(max_sum, second_sum + prefix_sum[j + firstLen] - prefix_sum[j])\n",
    "        return max_sum\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import accumulate\r\n",
    "class Solution:\r\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\r\n",
    "        presum = list(accumulate(nums, initial=0))\r\n",
    "        ans = 0\r\n",
    "        def f(firstLen, secondLen):\r\n",
    "            nonlocal ans\r\n",
    "            max_sum_first = 0\r\n",
    "            for i in range(firstLen+secondLen, len(presum)):\r\n",
    "                max_sum_first = max(max_sum_first, presum[i-secondLen]-presum[i-secondLen-firstLen])\r\n",
    "                ans = max(ans, max_sum_first + presum[i]-presum[i-secondLen])\r\n",
    "        f(firstLen, secondLen)\r\n",
    "        f(secondLen, firstLen)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        pre = list(accumulate(nums, initial=0))\n",
    "\n",
    "        def sumTwo(leftLen, rightLen):\n",
    "            first_max = float('-inf')\n",
    "            ret = float('-inf')\n",
    "            for second_end in range(leftLen + rightLen, 1 + len(nums)):\n",
    "                second_start = second_end - rightLen\n",
    "                first_max = max(first_max, pre[second_start] - pre[second_start-leftLen])\n",
    "                ret = max(ret, first_max+pre[second_end]-pre[second_end-rightLen])\n",
    "            return ret\n",
    "        return max(sumTwo(firstLen, secondLen), sumTwo(secondLen, firstLen)) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def pre_sum(self, nums):\n",
    "        res = [nums[0]] * len(nums)\n",
    "        for i in range(1, len(nums)):\n",
    "            res[i] = res[i-1] + nums[i]\n",
    "        return res\n",
    "\n",
    "    def pre_max(self, presum, length):\n",
    "        res = [presum[length-1]]\n",
    "        for i in range(length, len(presum)):\n",
    "            cur = presum[i] - presum[i-length]\n",
    "            res.append(max(res[-1], cur))\n",
    "        return res\n",
    "\n",
    "    def sums(self, premax, sufmax, start, end):\n",
    "        res = -float('inf')\n",
    "        # i为第二个子数组的起始位置\n",
    "        for i in range(start, end):\n",
    "            sum1 = premax[i-start]\n",
    "            sum2 = sufmax[i]\n",
    "            res = max(res, sum1+sum2)\n",
    "        return res\n",
    "\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        # f:first, s:second\n",
    "        \n",
    "        presum = self.pre_sum(nums)\n",
    "        # pre_max_f = self.pre_max(presum, firstLen)\n",
    "        # pre_max_s = self.pre_max(presum, secondLen)\n",
    "\n",
    "        sufsum = self.pre_sum(nums[::-1])\n",
    "        suf_max_f = self.pre_max(sufsum, firstLen)[::-1]\n",
    "        suf_max_s = self.pre_max(sufsum, secondLen)[::-1]\n",
    "        \n",
    "        # first_second = self.sums(pre_max_f, suf_max_s, firstLen, len(nums)-secondLen+1)\n",
    "        # second_first = self.sums(pre_max_s, suf_max_f, secondLen, len(nums)-firstLen+1)\n",
    "\n",
    "        first = presum[firstLen-1]\n",
    "        first_second = first + suf_max_s[firstLen]\n",
    "        for i in range(firstLen, len(nums)-secondLen):\n",
    "            first = presum[i] - presum[i-firstLen]\n",
    "            second = suf_max_s[i+1] # second = max(second, )\n",
    "            first_second = max(first_second, first+second) \n",
    "        \n",
    "        second = presum[secondLen-1]\n",
    "        second_first = second + suf_max_f[secondLen]\n",
    "        for i in range(secondLen, len(nums)-firstLen):\n",
    "            second = presum[i] - presum[i-secondLen]\n",
    "            first = suf_max_f[i+1]\n",
    "            second_first = max(second_first, second+first)\n",
    "\n",
    "        return max(first_second, second_first)\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        n=len(nums)       \n",
    "        s=list(accumulate(nums,initial=0))\n",
    "        def dfs(firstLen,secondLen):\n",
    "            ans,t=0,0\n",
    "            i=firstLen\n",
    "            while i+secondLen-1<n:\n",
    "                t=max(t,s[i]-s[i-firstLen])\n",
    "                ans=max(ans,t+s[i+secondLen]-s[i])\n",
    "                i+=1\n",
    "            return ans\n",
    "        return max(dfs(firstLen,secondLen),dfs(secondLen,firstLen))\n",
    "    \n",
    "                \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "        N = len(nums)\n",
    "        subSum1 = [0] * N \n",
    "        subSum2 = [0] * N \n",
    "\n",
    "        for i in range(firstLen-1, N):\n",
    "            subSum = 0\n",
    "            for j in range(i-firstLen+1,i+1):\n",
    "                subSum += nums[j]\n",
    "            subSum1[i] = subSum\n",
    "        \n",
    "        for i in range(secondLen-1, N):\n",
    "            subSum = 0\n",
    "            for j in range(i-secondLen+1, i+1):\n",
    "                subSum += nums[j]\n",
    "            subSum2[i] = subSum\n",
    "\n",
    "        \n",
    "        subMaxSum1 = subSum1[:]\n",
    "        subMaxSum2 = subSum2[:]\n",
    "\n",
    "        x = subMaxSum1[0]\n",
    "        y = subMaxSum2[0]\n",
    "\n",
    "        for i in range(1,N):\n",
    "            if subMaxSum1[i] <= x:\n",
    "                subMaxSum1[i] = x \n",
    "            else:\n",
    "                x = subMaxSum1[i]\n",
    "\n",
    "            if subMaxSum2[i] <= y:\n",
    "                subMaxSum2[i] = y \n",
    "            else:\n",
    "                y = subMaxSum2[i]\n",
    "\n",
    "        max_sum = 0\n",
    "        for i in range(firstLen+secondLen-1, N):\n",
    "            max_sum = max(subSum2[i] + subMaxSum1[i-secondLen], max_sum)\n",
    "        for i in range(firstLen+secondLen-1, N):\n",
    "            max_sum = max(subSum1[i] + subMaxSum2[i-firstLen], max_sum)\n",
    "\n",
    "        return max_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumTwoNoOverlap(self, nums: List[int], firstLen: int, secondLen: int) -> int:\n",
    "\n",
    "        # s = list(accumulate(nums, initial=0))  # nums 的前缀和\n",
    "        # ans = 0\n",
    "        # def f(firstLen: int, secondLen: int) -> None:\n",
    "        #     nonlocal ans\n",
    "        #     # maxSumA = 0\n",
    "        #     # for i in range(firstLen + secondLen, len(s)):\n",
    "        #     #     maxSumA = max(maxSumA, s[i - secondLen] - s[i - secondLen - firstLen])\n",
    "        #     #     ans = max(ans, maxSumA + s[i] - s[i - secondLen])\n",
    "        # f(firstLen, secondLen)  # 左 a 右 b\n",
    "        # f(secondLen, firstLen)  # 左 b 右 a\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        pre = list(accumulate(nums,initial = 0))\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        maxSumB = 0\n",
    "        while i+firstLen<=n:\n",
    "            j = i+firstLen\n",
    "            sumFir = pre[j]-pre[i]\n",
    "            while j+secondLen <= n:#pre可以取到n\n",
    "                sumSec = pre[j+secondLen] - pre[j]\n",
    "                ans = max(ans,sumFir+sumSec)\n",
    "                j += 1\n",
    "            \n",
    "            if secondLen <= i:\n",
    "                maxSumB = max(maxSumB,pre[i]-pre[i-secondLen])\n",
    "            ans = max(ans,sumFir+maxSumB)\n",
    "            i += 1\n",
    "        return ans \n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # l = min(firstLen,secondLen)\n",
    "        # r = max(firstLen,secondLen)\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate(nums,initial=0)) #s = list(accumulate(stones, initial=0))\n",
    "        if firstLen + secondLen == n:\n",
    "            return pre[-1]\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        # print(pre)\n",
    "        while i+firstLen<=n:\n",
    "            j = i + firstLen \n",
    "            firstsum = pre[j] - pre[i]\n",
    "            secendsum = 0\n",
    "            # print(\"fir\",i,firstLen,firstsum,j)\n",
    "            while j+secondLen<=n:\n",
    "                # print(j,j+secondLen)\n",
    "                secendsum = max(secendsum,pre[j+secondLen]-pre[j])\n",
    "                j += 1\n",
    "            j = 0\n",
    "            while j+secondLen<=i:\n",
    "                secendsum = max(secendsum,pre[j+secondLen]-pre[j])\n",
    "                j += 1\n",
    "            # print(\"sec\",secendsum)\n",
    "            ans = max(ans,firstsum+secendsum)\n",
    "            i += 1\n",
    "        return ans\n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
